<html>
    <head>
    <link rel="stylesheet" href="lmm.css" type="text/css" />
    </head>
<body class="lmm">
.C This file is part of the Lisp Machine manual.   -*-Text-*-
.C MUST WRITE SECTIONS FOR FEFS, ARRAYS, STACK GROUPS.
<!-- also a section e xplaining the low level implementation of closures. -->

<div class='chapter'>4. Internal Formats</div><p class='cindent'><!-- internal formats -->

	This chapter explains the internal formats used within the
Lisp Machine.  They have been changed in the past and will change
in the future, and so no programs should depend on any information
in this chapter.

	The values of the symbolic field mentioned in this chapter
are set in the file [MIT-AI]LISPM; QCOM &gt;; this file is the ultimate
authority on the exact format of objects, and should be consulted
if more information is required.

<div class='section'>4.1 </div>
	A Lisp Object is represented by a <font class="italic">Lisp Pointer</font>, or
<font class="italic">pointer</font> for short.  Some pointers point to asociated <font class="italic">storage</font> in
the Lisp Machine's virtual memory.  A pointer is 29. bits long, and has
two fields: the high-order five bits are called the <font class="italic">data type</font>
field, and the low-order 24. bits are called the <font class="italic">address</font> field.
The data type field (or <font class="italic">type field</font>) contains a numeric code, whose
value determines the interpretation of the address field.  The symbolic
names for these two fields are <font class="lisp">%%q-data-type</font> and <font class="lisp">%%q-pointer</font>
(the latter name is somewhat unfortunate).  Symbols by these names
exist in the initial Lisp environment and are bound to appropriate byte
specifiers.  Pointers are always stored left-justified within 32. bit
words.  The highest-order 3 bits of the word are not part of the
pointer; their use in memory is explained below.

	Here are the currently defined values for the data type field
of a Lisp pointer.  For each value, a symbol exists in the initial
environment that are bound to the corresponding values of the data type
field.

	Not all Lisp pointers are actually legal Lisp values.  Some of
the types of pointer are used for error-checking, and others may
exist in memory but are never passed around as arguments to functions
nor treated as Lisp objects in any way.  The data type values listed
below are grouped together to clarify this.



.table 3
.item dtp-trap
.vindex dtp-trap
This value is illegal, and the processor will halt if it references a pointer
with data type <font class="lisp">dtp-trap</font>.  The value of <font class="lisp">dtp-trap</font>
is zero; the intention is to catch errors in which a data type field is uninitialized.
.item dtp-null
.vindex dtp-null
This


	Here are the data type values which are used in pointers that
are Lisp objects.

.table 3
.item dtp-symbol
.vindex dtp-symbol
A pointer with this data type is a Lisp symbol.
The address field is the address of a five-word block of memory.
The first word contains a <font class="lisp">dtp-symbol-header</font> pointer, which
is the print-name of the symbol.  The second word is the <font class="italic">value cell</font>;
if the symbol is bound, it contains a pointer which is the value of the symbol.  If the symbol
is unbound, the pointer has data type <font class="lisp">dtp-null</font>, and its address is
the address of the symbol.  The third word is the function cell; its contents is
the current definition of the symbol, and it is interpreted just like the value cell.
The fourth cell is the property list cell, whose contents is the property list.
It is normally either of <font class="lisp">dtp-list</font> or <font class="lisp">nil</font>.  The fifth cell is the
package cell; if the symbol is interned, it contains the package of the symbol,
otherwise <font class="lisp">nil</font>.  The high three bits of the five words are not used.
.item dtp-fix
.vindex dtp-fix
A pointer with this data type is a Lisp fixnum.
The address field is the value of the number, in 24. bit two's complement
notation.
.item dtp-extended-number
.vindex dtp-extended-number
A pointer with this data type is some kind of Lisp number other than a
fixnum or small-flonum.  The address field is the address of a block of
memory, the first word of which is of data type <font class="lisp">dtp-header</font> (see
below).  The value of the header type field is one of
<font class="lisp">%header-type-flonum</font> or <font class="lisp">%header-type-bignum</font>, and the Lisp data
type of the object is either flonum or bignum, respectively.  The
values <font class="lisp">%header-type-complex</font> and <font class="lisp">%header-type-rational-bignum</font>
are also defined and are used in headers pointed to by
<font class="lisp">dtp-extendec-number</font> pointers, but are not yet implemented.

Flonums use the remaining 19. bits of the <font class="lisp">dtp-header</font> word as two
fields.  The high-order 11. bits hold the exponent, in excess-2000
notation.  The low-order 8. bits hold the uppermost 8. bits of the
mantissa.  The word following the header holds the lowermost 24. bits
of the mantissa in its low-order 24. bits; its high-order 8. bits are
not used.  The mantissa is 32. bits in all.  Flonums are always
normalized, and the sign bit of the mantissa <font class="italic">is</font> stored (unlike
small flonums), as the highest-order bit of the 32. bit mantissa.

Bignums also use the remaining 19. bits of the <font class="lisp">dtp-header word as two
fields.  The high-order bit is 0 if the number is positive, and 1 if it
is negative (a bignum may never be zero; in fact, it may never have any
value that is expressible by a fixnum).  The low-order 18. bits hold
the length of the bignum in words, not counting the header word, as an
unsigned number.  There follow that many words.  Each of the following
words holds 31. bits of the binary representation of the absolute value
of the number in its low-order 31. bits.  The high-order bits are
always zero.  The first word is the lowest-order word, and the last is
the highest-order.  There must be at least one word.  Note that since
these words do not contain Lisp pointers, they are not cells, and no
pointer may point at them.
.item dtp-locative
.vindex dtp-locative
A pointer with this data type is a Lisp locative.
The address field contains the address of the locative's cell,
and may be any cell in the Lisp environment.
.item dtp-list
.vindex dtp-list
A pointer with this data type is a Lisp <font class="italic">cons</font>.  The address
field contains the address of a word, the low-order 29. bits of
which hold a pointer which is the car of the cons. The two high-order
bits of the word are called the <font class="italic">cdr code</font> field, and indicate
what the cdr of the cons is.  The cdr code may have any of the following
values; the initial Lisp enviroment contains symbols of these names whose
values are the corresponding values of the cdr code field.
.table 3
.item cdr-normal
.vindex cdr-normal
The cdr of the cons is contained in the low-order 29. bits of the word
following the word pointed to by the <font class="lisp">dtp-list</font> pointer.  The high
two bits of this following word should contain <font class="lisp">cdr-error</font>, so
that any <font class="lisp">dtp-list</font> pointer pointing at it will be caught as an error.
.item cdr-error
.vindex cdr-error
The pointer is illegal; see above.
.item cdr-next
.vindex cdr-next
The cdr of the cons is a pointer whose data type is <font class="lisp">dtp-list</font>,
and whose address is one greater than the address field of the
original cons pointer.
.item cdr-nil
.vindex cdr-nil
The cdr of the cons is the symbol <font class="lisp">nil</font>.
.end_table
The reason for the inclusion of the <font class="lisp">cdr-next</font> and <font class="lisp">ccccdr-nil</font> codes is
that most conses form cdr-linked lists; by using these cdr codes, a list of <font class="italic">n</font>
elements may be stored as <font class="italic">n</font> contiguous cells, the first <font class="italic">n-1</font> of which
have cdr code <font class="lisp">cdr-next</font> and the last of which contains <font class="lisp">cdr-nil</font>.
Were the list stored in the more general <font class="lisp">cdr-normal</font> form, it would occupy
twice as much storage.
.item dtp-u-entry
.vindex dtp-u-entry
A pointer of this type is a microcode compiled-code object.
The address field contains a small unsigned number which is an
index into various special tables.
.item dtp-fef-pointer
.vindex dtp-fef-pointer
A pointer of this type is a macrocode compiled-code object.
Its format is quite involved, and is explained in a later section
of this chapter.  The address field is the address of a <font class="lisp">dtp-header</font>
word whose header type is <font class="lisp">%header-type-fef</font>.  "FEF" is an acronym
for <font class="italic">Function Entry Frame</font>.
.item dtp-array-pointer
.vindex dtp-array-pointer
A pointer of this type is an array.  The format of arrays
is quite complex, and is explained in a later section of this chapter.
The address field is the address of a <font class="lisp">dtp-array-header</font> word.
.item dtp-stack-group
.vindex dtp-stack-group
A pointer of this type is a stack group.  The format of stack groups
is quite complex, and is explained in a later section of this chapter.
The address field is the address of a <font class="lisp">dtp-array-header</font> word.
.item dtp-closure
.vindex dtp-closure
A pointer of this type is a closure.  The format of a closure
is the same as that of a list (see <font class="lisp">dtp-list</font> above),
except that it is very restrictive.  The pointer must be to a list
of an odd number of elements.  The first element is the function-object
associated with the closure; it may be any Lisp object.  The rest
of the elements must be locatives, are considered as pairs; there is one pair of elements
for each variable closed over.  The first locative of a pair points to
the value cell of the variable.  The second locative points to
a word called an <font class="italic">external value cell</font>; its two high-order bits
must contain <font class="lisp">cdr-nil</font> (see <font class="lisp">dtp-list</font> above), and its low
29. bits contain a pointer which is the saved value for the symbol.
[Maybe move this to a section, and explain what CLOSURE and calling
one do?]
.item dtp-small-flonum
.vindex dtp-small-flonum
A pointer of this type is a small flonum.
The address field is divided into two parts.  The high 7. bits
contain the exponent, in excess-100 notation.  The low 17.
bits contain the mantissa.  Small flonums are always normalized,
and the sign bit of the mantissa is <font class="italic">not</font> stored (unlike
regular flonums).
.item dtp-select-method
.vindex dtp-select-method
[To be supplied.]
.item dtp-instance
.vindex dtp-instance
[To be supplied.]
.item dtp-entity
.vindex dtp-entity
[To be supplied.]
.end_table

	Here are the data type codes used for error checking.  Pointers
with these data types are not Lisp objects, and may not be passed around as 
arguments, nor returned from functions.
.table 3
.item dtp-trap
.vindex dtp-trap
The value of <font class="lisp">dtp-trap</font> is zero, and is considered illegal in order
to increase the likelyhood that an uninitialized data type field will
be reported as an error.
.item dtp-null
.vindex dtp-null
Pointers with this data type are stored in value and function cells of symbols
to indicate that the symbol is unbound or undefined, respectively (see <font class="lisp">dtp-sy,bol</font>
above).  The address field is the address of the symbol.
.item dtp-free
.vindex dtp-free
Some of the unallocated storage in the Lisp Machine's memory (see the discussion of
areas, (areas)) contains words of this data type, to increase the likelyhood
that a reference to unallocated storage will be reported as an error.
.end_table

	Here are the data type codes used for header words.  Pointers
with these data types are not Lisp objects, and may not be passed around as 
arguments, nor returned from functions.  The reasons that headers are used
the way they are are explained in the section on the storage conventions
(see (storage-convention)).

.table 3
.item dtp-symbol-header
.vindex dtp-symbol-header
The first word of the five word block pointed to by symbols (see <font class="lisp">dtp-symbol</font>
above) has this data type.  The address is the address of an array header,
and in fact the <font class="lisp">dtp-symbol-header</font> word is treated as if it were
of type <font class="lisp">dtp-array-pointer</font>, except that it is considered to be a header
by the garbage collector.  (The <font class="lisp">get-pname</font> function returns a <font class="lisp">dtp-array-pointer</font>
object whose address is the address of the symbol's header.)  The format of
arrays is explained in a later section.  The array pointed to by the <font class="lisp">dtp-symbol-header</font>
is the print-name of the symbol.
.item dtp-array-header
.vindex dtp-array-header
The word pointed to by words of data type <font class="lisp">dtp-array-pointer</font>, <font class="lisp">dtp-stack-group</font>,
or <font class="lisp">dtp-symbol-header</font> is of this data type.  The format of arrays is explained
in a later section.
.item dtp-header
.vindex dtp-header
This header is used for many kind of objects.  Its address field is divided
into two fields.  The high-order 5. bits (<font class="lisp">%%header-type-field</font>) contains
an unsigned number indicating what type of header it is; the meaning of the low-order 19. bits
(<font class="lisp">%%header-rest-field</font>) depends of the value of the <font class="lisp">%%header-type-field</font>.
The values the <font class="lisp">%%header-type-field</font> may contain are:
.table 3
.item %header-type-error 
.vindex %header-type-error 
The header is illegal.  The value of this field is zero.
.item %header-type-fef
.vindex %header-type-fef
This is the header of a FEF (Function Entry Frame).
.item %header-type-array-leader
.vindex %header-type-array-leader
This is the first word of an array with a leader.
.item %header-type-flonum
.vindex %header-type-flonum
This is the header of a (non-small) flonum.
.item %header-type-bignum
.vindex %header-type-bignum
This is the header of a bignum.
.end_table

	The values <font class="lisp">%header-type-complex</font> and
<font class="lisp">%header-type-rational-bignum</font> are reserved for future
implementation.  The format of the rest of the <font class="lisp">dtp-header</font> word
depends on the value of the <font class="lisp">%%header-type-field</font> and is explained
with the documentation of the corresponding Lisp type.
.item dtp-instance-header
.vindex dtp-instance-header
[To be supplied.]
.end_table

	Here are the data type codes used for <font class="italic">forwarding pointers</font>
(also called <font class="italic">invisible pointers</font>).  Pointers with these data types
are not Lisp objects, and may not be passed around as  arguments, nor
returned from functions.

	The fundamental idea behind forwarding pointers is that when the
processor reads a word from memory, it checks the data type field of
the word to see if the word is an forwarding pointer, and if it is,
the processor reads the contents of the word addressed by the forwarding
pointer and returns that word instead.  In other words, the forwarding
pointer says "don't use my location, use <font class="italic">that</font> location instead."

	In fact, some of the forwarding pointers act this way for only
certain types of reference, and and not for others.  When there is a
type of reference for which this action is taken upon sight of an
forwarding pointer, we say that the pointer is invisible for that
operation; when this action is not taken, we say that the pointer is
visible.  A <font class="lisp">dtp-locative</font> pointer is visible for all operations (it
is described above).

	Forwarding pointers may be chained together to any depth.

.table 3
.item dtp-one-q-forward
.vindex dtp-one-q-forward
This is the simplest kind of forwarding pointer; it is used to
forward one word to some other word.
.item dtp-external-value-cell-pointer
.vindex dtp-external-value-cell-pointer
This kind of forwarding pointer is used for the implementation of
closures; words of this type are usually found in value cells and
function cells of symbols.  It is different from the
<font class="lisp">dtp-one-q-forward-</font> in that such a word is <font class="italic">visible</font> to the
<font class="italic">bind</font> or <font class="italic">unbind</font> operations.  The reason for this is explained
in the section on the implementation of closures (see (closure-implementation)).
.item dtp-header-forward
.vindex dtp-header-forward
This kind of forwarding pointer is used to forward an entire structure
(see (storage-conventions)) somewhere.  The header of the structure is
replaced with a <font class="lisp">dtp-header-forward</font> word, and the rest of the
structure is replaced by <font class="lisp">dtp-body-forward</font> words.  The difference
between a <font class="lisp">dtp-header-forward</font> and a <font class="lisp">dtp-one-q-forward</font> is that if
the word pointed to by a <font class="lisp">dtp-array-pointer</font> pointer were moved and a
<font class="lisp">dtp-one-q-forward</font> word were left behind, references to that array
would find the contents of the header word at the forwarded location,
but would find the array elements based on the location unforwarded
address (in words following the <font class="lisp">dtp-one-q-forward</font> word).  If a
<font class="lisp">dtp-header-forward</font> were used, not only the header word itself but
the entire contents of the array would be found at the new location.
.item dtp-body-forward
.vindex dtp-body-forward
This kind of forwarding pointer is used in conjunction with the
<font class="lisp">dtp-header-forward</font> data type (see above) to forward whole
structures.  The functionality of <font class="lisp">dtp-body-forward</font> is similar to
that of <font class="lisp">dtp-one-q-forward</font>, but the two must be distinuished
for purposes of storage conventions (see (storage-conventions)).
.item dtp-gc-forward
.vindex dtp-gc-forward
Words of this tdata type are not really forwarding pointers; they
are used by the copying garbage collector and are only
found in "oldspace" regions.  See (gc).
.end_table

<div class='section'>4.2 </div>
	A FEF (Function Entry Frame) is a compiled-code object,
generally produced by the Lisp compiler.  It is represented by
a pointer of data type <font class="lisp">dtp-fef-pointer</font>.  The address of
the pointer is the first word of a block of memory, the first
six words of which are a header with various fields.  The following
is a table of these fields, listed under names of Lisp macros
that access them given a FEF.

.table 3
.item si:fef-name
.mindex si:fef-name
The name of the FEF, as a string.
.item si:fef-initial-pc
.mindex si:fef-initial-pc
The first half-word of macro-code in the FEF, as a fixnum
in halfwords relative to the base of the FEF.
.item si:fef-no-adl-p
.mindex si:fef-no-adl-p
If this bit is on, the ADL is not present.
.item si:fef-fast-argument-option-p
.mindex si:fef-fast-argument-option-p
If this bit is on, the "fast argument option" is in effect.
.item si:fef-specials-bound-p
.mindex si:fef-specials-bound-p
If this bit is on, entry to this function binds some special variables.
.item si:fef-length
.mindex si:fef-length
The length of the FEF, as a fixnum in words.
.item si:fef-fast-argument-option-word
.mindex si:fef-fast-argument-option-word
The numeric argument descriptor word of the FEF.
.item si:fef-bit-map-p
.mindex si:fef-bit-map-p
If this bit is on, the <font class="lisp">si:fef-bit-map</font> describes the special
variable bindings of the function; otherwise the <font class="lisp">si:fef-bit-map</font>
is meaningless.
.item si:fef-bit-map
.mindex si:fef-bit-map
A bit map of special variables; see below.
.item si:fef-number-of-locals
.mindex si:fef-number-of-locals
The number of local variables used by this function.
.item si:fef-adl-origin
.mindex si:fef-adl-origin
The address of the first cons of the ADL, as a fixnum in words
relative to the base of the FEF.
.item si:fef-adl-length
.mindex si:fef-adl-length
The number of elements of the ADL.
.end_table

	</body>
</html>

